// @algorithm @lc id=75 lang=cpp 
// @title sort-colors


// @test([2,0,2,1,1,0])=[0,0,1,1,2,2]
// @test([2,0,1])=[0,1,2]
// @test([0])=[0]
// @test([1])=[1]
// @test([1,2,0])=[0,1,2]
// @test([0,1,0])=[0,0,1]
// @test([2,0,2,1,1,0])=[0,0,1,1,2,2]
// @test([2,2,1])=[1,2,2]
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int front = 0, back = nums.size() - 1;
        for(int i=front; i<=back; i++){
            while(2==nums[i] && i<=back)
                swap(nums[i], nums[back--]);
            if(0==nums[i])
                swap(nums[i], nums[front++]);
        }
    }
};